/**
 * 给定两个大小相等的数组nums1和nums2，nums1相对于 nums的优势可以用满足nums1[i] > nums2[i]的索引 i的数目来描述。
 *
 * 返回 nums1的任意排列，使其相对于 nums2的优势最大化。
 *
 * 链接：https://leetcode.cn/problems/advantage-shuffle
 * 基本思路：这题就像田忌赛马的情景，nums1 就是田忌的马，nums2 就是齐王的马，数组中的元素就是马的战斗力，你就是谋士孙膑，请你帮田忌安排赛马顺序，使胜场最多。
 * 最优策略是将齐王和田忌的马按照战斗力排序，然后按照战斗力排名一一对比：
 * 如果田忌的马能赢，那就比赛，如果赢不了，那就换个垫底的来送人头，保存实力。
 * 详细解法：https://labuladong.gitee.io/algo/2/20/32/
 */
class AdvantageCount {//田忌赛马思路，nums1是田忌的马，nums2是齐王的马
    public int[] advantageCount(int[] nums1, int[] nums2) {
         PriorityQueue<int[]> qu=new PriorityQueue<>((o1,o2)->{
            return o2[1]-o1[1];
        });
        int len2=nums2.length;
        for(int i=0;i<len2;i++) {//给nums2降序排序
            qu.offer(new int[]{i,nums2[i]});
        }
        Arrays.sort(nums1);//给nums1升序
        int len1=nums1.length;
        int left=0;
        int right=len1-1;//nums1[left]表示最弱的马，nums1[right]表示最强的马
        int[] ans=new int[len1];
        while(!qu.isEmpty()) {
            int[] tmp=qu.poll();
            if(tmp[1]<nums1[right]) {//当nums1中最快的马能比得过nums2中最快的马的时候，就拿出去比
                ans[tmp[0]]=nums1[right];
                right--;
            } else {//当nums1中最快的马比不过nums2中最快的马或者和nums2中最快的马一样快时，就拿最弱的马去送人头
                ans[tmp[0]]=nums1[left];
                left++;
            }
        }
        return ans;
    }
}